//外星语言是否排序
class Solution {
public:
    int findMinDifference(vector<string>& timePoints) 
    {
        sort(timePoints.begin(),timePoints.end());
        int res=INT_MAX;
        int pre=gettime(timePoints[0]);
        for(int i=1;i<timePoints.size();i++)
        {
            int cur=gettime(timePoints[i]);
            res=min(res,cur-pre);
            pre=cur;
        }
        res=min(res,gettime(timePoints[0])+1440-pre);
        return res;
    }
    int gettime(string& str)
    {
        // int num=(stoi((str[0]-'0'))*10+stoi(str[1]-'0'))*60;
        // int num2=stoi((str[3]-'0'))*10+stoi(str[4]-'0');
        int num1=(int)(str[0]-'0')*10+(int)(str[1]-'0');
        int num2=(int)(str[3]-'0')*10+(int)(str[4]-'0');
        return num1*60+num2;
    }
};

//字符串交织

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) 
    {
        if(s1.size() + s2.size() != s3.size()) 
        {
            return false;
        }
        //dp[i][j] s1的前i个字符和s2的前j个字符 能否组成s3的前(i+j)个字符
        vector<vector<bool>> dp(s1.size()+1,vector<bool>(s2.size()+1,false));
        dp[0][0]=true;
        for (int j = 0; j < s2.size() && s2[j] == s3[j]; ++j) 
        {
            dp[0][j+1] = true;
        }
        for(int i = 0; i < s1.size() && s1[i] == s3[i]; ++i) 
        {
            dp[i+1][0] = true;
        }
        for (int i = 0; i < s1.size(); ++i)
        {
            for (int j = 0; j < s2.size(); ++j)
            { 
                char ch1 = s1[i];
                char ch2 = s2[j];
                char ch3 = s3[i + j + 1];
                dp[i + 1][j + 1] = ((ch1 == ch3) && dp[i][j + 1]) 
                || ((ch2 == ch3) && dp[i + 1][j]);
           }
        }
        return dp[s1.size()][s2.size()];
    }
};
//最小时间差
class Solution {
public:
    int findMinDifference(vector<string>& timePoints) 
    {
        sort(timePoints.begin(),timePoints.end());
        int res=INT_MAX;
        int pre=gettime(timePoints[0]);
        for(int i=1;i<timePoints.size();i++)
        {
            int cur=gettime(timePoints[i]);
            res=min(res,cur-pre);
            pre=cur;
        }
        res=min(res,gettime(timePoints[0])+1440-pre);
        return res;
    }
    int gettime(string& str)
    {
        // int num=(stoi((str[0]-'0'))*10+stoi(str[1]-'0'))*60;
        // int num2=stoi((str[3]-'0'))*10+stoi(str[4]-'0');
        int num1=(int)(str[0]-'0')*10+(int)(str[1]-'0');
        int num2=(int)(str[3]-'0')*10+(int)(str[4]-'0');
        return num1*60+num2;
    }
};